package airthmetic.exercise.dp;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class _322_零钱兑换 {


    public static void sort(int[] nums){
        Arrays.sort(nums);
        int n = nums.length - 1;
        int temp;
        for(int i=0; i< (n >> 1); i++){
            // swap
            temp = nums[i];
            nums[i] = nums[n-i];
            nums[n-i] = temp;
        }
    }

    public static void main(String[] args) {
        // 纯贪心
        int[] coins= new int[]{5,2,1};
        int amount = 8;
        System.out.println(coinChange(coins, amount));
        System.out.println("===================================分割线===================================");


        // 贪心+回溯
        int[] coins2= new int[]{10,9,1};
        int amount2 = 18;
        System.out.println(coinChange2(coins2, amount2));
        System.out.println("===================================分割线===================================");

        // 纯回溯
        int[] coins3= new int[]{10,9,1};
        int amount3 = 18;
        System.out.println(coinChange3(coins3, amount3));
        System.out.println("===================================分割线===================================");

        // 动态规划
        int[] coins4 = new int[]{411,412,413,414,415,416,417,418,419,420,421,422};
        int amount4 = 9864;
        System.out.println(coinChange4(coins4, amount4));
    }

    // 纯贪心
    public static int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        int returnAmount = 0;
        Arrays.sort(coins);
        for(int i=coins.length - 1; i>=0; i--){
            int currentCount = amount / coins[i];
            if(currentCount == 0){
                continue;
            }
            returnAmount += currentCount;
            amount = amount - (currentCount * coins[i]);

            if(amount == 0){
                return returnAmount;
            }
        }

        return -1;
    }


    // 贪心 + 回溯
    public static int coinChange2(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        sort(coins);
        backtrack(coins, amount, 0, 0);
        return minCount == Integer.MAX_VALUE ? -1 : minCount;
    }

    public static int minCount = Integer.MAX_VALUE;

    // 回溯+贪心思想
    public static void backtrack(int[] coins, int amount, int startIndex, int selectedCount){
        // terminal
        if(amount == 0){
            if(minCount > selectedCount){
                minCount = selectedCount;
            }
            return;
        }
        if(startIndex == coins.length){
            return;
        }
        // process current logic
        int currentAmount = amount / coins[startIndex];
        for(int i=currentAmount; i>=0 && selectedCount+i < minCount; i--){
            int drillDownAmount = amount - coins[startIndex] * i;
            // drill down
            // 无需手动的撤销选择，因为drillDownAmount是当前层的变量，向下传当前层变量，回溯回来的时候amount是上一层传下来的变量
            backtrack(coins, drillDownAmount, startIndex + 1, selectedCount + i);
        }
    }


    // 纯回溯
    public static int coinChange3(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        int minCount = Integer.MAX_VALUE;
        for(int i=0; i < coins.length; i++){
            if(coins[i] > amount){
                continue;
            }
            int rearCount = coinChange3(coins, amount - coins[i]);
            if(rearCount == -1){
                continue;
            }
            if(minCount > rearCount +1){
                minCount = rearCount + 1;
            }
        }

        return minCount == Integer.MAX_VALUE ? -1 : minCount;

    }

    // 动态规划
    public static int coinChange4(int[] coins, int amount) {
        /*
        * 动态规划思考问题
        *
        * 1.确定状态参数/状态和选择
        *   状态  在子问题与原问题之间变化的值  此题为amount
        *   选择/决策 做选择会让状态变更并且逐渐趋近于原问题
        *     for(int coin : coins){
        *     }
        * 2.定义dp数组(dp table)的含义： 子问题需要缓存起来在后续使用，一般dp数组中存储的值就是我们问题需要返回的结果。
        *   dp[i]: 如果能从coins中找到对应的硬币个数凑成金额i,那么所需要的最少硬币个数即dp[i]的值
        * 3.确定初始状态的值
        *   dp[0] = 0;
        * 4.确定状态转移的逻辑 （状态转移公式） 怎么根据子问题求解原问题
        *   在这一步我们动态规划的思想是：通过子问题的解来推导原问题的解
        *   也就是说：如果你已经计算出dp[0],dp[1]...dp[i-2],dp[i-1]的值之后，你如何去计算出dp[i]的值
        *   当然这个过程是通过我们做选择来让状态发生转移的
        *   此处的状态转移公式为
        *    for(int coin : coins){
        *       dp[i] = dp[i-coin] + coin (dp[i-coin] + 1)
        *       dp[i] = Math.min(dp[i], dp[i-coin] + 1);
        *   }
        * */


        /**
         动态规划思想解决问题
         因为此题具备重叠子问题和无后效性以及最优子结构所以可以用动态规划思想解决问题
         1.确定状态参数和选择
         状态参数：状态参数是子问题与原问题之间不断变化的值
         此题的状态参数是amount
         选择/决策：做选择使状态参数不断变化并趋近于原问题的解
         此题的选择是coins[i]

         2. 定义dp table的含义
         动态规划的思想是根据子问题的解推导原问题
         int[] dp = new int[];
         此题dp table的含义是 dp[i]是凑成i元需要的最少硬币个数

         3. 初始化dp table
         此题dp[0]为0，因为凑成amount 0 需要0个硬币
         dp[i]要给一个初始值，这里给amount + 1，因为整数数组，最小的硬币可能是1，凑成金额i最多用i个1元

         4. 推导状态转移公式
         动态规划的思想是根据子问题的解推导原问题
         即我们得知dp[0]...d[1]...dp[i-2]...dp[i-1]的解之后怎么推导出dp[i]的值
         此题的转移逻辑是：当前需要凑成的金额i,减去for()循环,当前循环的硬币面额，得到的是凑成i-coin需要的最少硬币个数(子问题已被求解，直接去dp table拿)。在子问题上加上当前硬币就是需要的最少硬币个数
         for(int i=1; i<=amount; i++){
         for(int coin : coins){
         dp[i] = Math.min(dp[i], dp[coin - i] + 1);
         }
         }
         */
        //构造dp数组(缓存中间的状态信息/子问题的最优解/状态参数的值)
        int[] dp = new int[amount+1];
        //初始填充一个不可能的值,对应面额amount最多的组合就是amount个1的组合，需要
        //amount个硬币,所以amount+1是不可能的
        Arrays.fill(dp,amount+1);
        //初始状态赋值
        dp[0] = 0;//amount=0无需硬币组合
        // 对每种状态的每种取值进行遍历
        //从子问题开始求解,推导到大问题，外层循环遍历所有状态的所有取值
        for (int i=1;i<=amount;i++) {
        //对每个子问题i，在coins中找能满足子问题i的众多解中的最优解(最少硬币数量)，
            //内层 for 循环在求所有选择的最小值
            for (int coin:coins) {
                if (coin <= i) { //coin>子问题i，该硬币无法构成最终解,直接跳过
                    /*
                    1:直接从dp中拿出求解问题i所依赖的子问题(i-coin)的最优解,
                    2:dp[i-coin] + 1即当前子问题i选择该coin的最优解
                    3:dp[i] = Math.min(dp[i],dp[i-coin]+1);是在众多解中选出一个
                    最优的作为子问题i的最优解。
                    */
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }

        return (dp[amount]==amount+1) ? -1:dp[amount];
    }


    // 动态规划
    public static int coinChange5(int[] coins, int amount) {
        /*
         * 动态规划思考问题
         * 1.确定状态参数和选择决策
         *   状态参数是在原问题与子问题之间变化的值。
         *   此题为amount
         *
         *   选择/决策：通过做选择使状态参数不断变化，并趋近于原问题的解
         *   此题为coins数组
         *
         * 2.定义dp数组的含义(dp table)
         *   利用子问题推导原问题的时候子问题需要缓存起来
         *   此题的定义为：dp[i]为凑成i需要的最少硬币个数
         *
         * 3.初始化dp数组
         *   初始化此题为dp[0] = 0
         *   因为凑成0元的硬币个数为0
         *
         * 4.状态转移逻辑
         *   状态转移公式，在动态规划的思想中，利用子问题推导原问题
         *   此题为：
         *   for(int i=1; i<=amount; i++){
         *      for(int j=0; j<coins.length; j++){
         *          dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
         *      }
         *   }
         *
         * */

        int[] dp = new int[amount + 1];
        Arrays.fill(dp,amount + 1);
        dp[0] = 0;

        for(int i=1; i<=amount; i++){
             for(int j=0; j<coins.length; j++){
                 if(i-coins[j] < 0){
                     continue;
                 }
                 dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
             }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];

    }


}
